#include<iostream>

//模板类:模板化的是 成员变量的类型

// 类模板的 名字 不能单独作为 一个类型 出现
// 得跟模板的 类型参数 一起
// 类模板的定义  必须要 显式调用

//类模板的 声明 和 定义 不能分开

template<typename T>
class DynamicArray
{

public:
    DynamicArray();
    DynamicArray(const DynamicArray & array );


    ~DynamicArray();

    DynamicArray& operator=(const DynamicArray& array);

    void InsertTail(const T& element);



    void InsertHead(const T&element);


    void InsertByIndex(const T&element,int index);

    void RemoveByIndex(int index);


    T FindByIndex(int index);
    

    
    DynamicArray<int> FindByElement(T element);
    

   
    void RemovrByElement(T element);
    

    template<typename U>   
    friend std::ostream & operator<<(std::ostream& os,const DynamicArray<U>& array);
    
    template<typename Display>
    void show(Display display);


private:
    T *a;
    int size;
    int capacity;
};

//函数类外 定义
template<typename T>
DynamicArray<T>::DynamicArray()
{
    this->capacity = 15;
    this->size = 0;
    a = new T[capacity];
}



template<typename T>
DynamicArray<T>::DynamicArray(const DynamicArray<T> & array )
{
    a = new T[capacity];
    for (int i = 0; i < size; ++i)
    {
        a[i] = array.a[i];
    }
    this->capacity = array.capacity;
    this->size = array.size;
}


template<typename T>
DynamicArray<T>::~DynamicArray()
{
    delete []a;
}

template <typename T>
inline void DynamicArray<T>::InsertTail(const T &element)
{
    if(size >= capacity)
    {
        capacity *=2;
        T *newptr = new T[capacity];
        for(int i=0;i<size;i++)
        {
            newptr[i] = a[i];
        }
        
        delete[] a;
        a = newptr;
    }
    a[size++] = element;
}

template <typename T>
inline void DynamicArray<T>::InsertHead(const T &element)
{
        if(size >= capacity)
    {
        capacity *=2;
        
        T *newptr = new T[capacity];
        
        for(int i=0; i < size ; i++)
        {
            newptr[i] = a[i];
        }

        delete[] a;
        a = newptr;
    }
    
    for(int i = size;i > 0;i--)
    {
        a[i] = a[i-1];
    }

    a[0] = element;
    this->size++;
}

template <typename T>
inline void DynamicArray<T>::InsertByIndex(const T &element, int index)
{
    if(index < 0 && index > size)
    {
        std::cout<<"非法插入位置\n";
    }

    if(size >= capacity)
    {
        capacity *=2;
        T *newptr = new T[capacity];
        for(int i=0; i < size ; i++)
        {
            newptr[i] = a[i];
        }
        
        delete[] a;
       
        a = newptr;
    }

    for(int i = size;i > index;i--)
    {
        a[i] = a[i-1];
    }
    
    a[index] = element;
    this->size++;

}

template <typename T>
inline void DynamicArray<T>::RemoveByIndex(int index)
{
    if(index >= 0 && index < size)
    {
        for(int i = index;i < size - 1 ;i++)
        {

            this->a[i] = this->a[i + 1];
        }
    }
    else
        return;
    this->size--;
}


template <typename T>
inline DynamicArray<T>& DynamicArray<T>::operator=(const DynamicArray<T>& array)
{
    this->size = array.size;
    this->capacity = array.capacity;
    
    delete[] a;
    a = new T[capacity];
    for(int i=0;i<capacity;i++)
    {
         this->a[i] = array.a[i];
    }

    return *this;
}


template<typename T>
template<typename Display>
void DynamicArray<T>::show(Display display)
{
    for(int i=0 ; i<size ; i++)
    {
        display(a[i]);
    }
}


template<typename T>
std::ostream & operator<<(std::ostream& os,const DynamicArray<T>& array)
{
    for(int i= 0 ; i < array.size ; i++ )
    {
        std::cout<<array.a[i]<<" ";
    }
    return os;
    std::cout<<std::endl;
}


template<typename T>
T DynamicArray<T>::FindByIndex(int index)
{
    if(index < 0 || index >= this->size)
    {
        std::cout<<"无法找到这个位置的数!"<<std::endl;

    }
    return this->a[index];
}

template <typename T>
inline DynamicArray<int> DynamicArray<T>::FindByElement( T element)
{
    DynamicArray<int> result;
    
    for(int i=0;i<this->size;i++)
    {
        if(this->a[i] == element )

        result.InsertTail(a[i]);
    }

    return result;
}

template <typename T>
inline void DynamicArray<T>::RemovrByElement(T element)
{
     for(int i=0;i<this->size;i++)
    {
        if(a[i]==element)
        {
            RemovrByIndex(i);
            i--;
        }
    }
}
